/*
 * ModelCC, distributed under ModelCC Shared Software License, www.modelcc.org
 */

package org.modelcc.language.syntax;

import java.io.Serializable;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import org.modelcc.language.metamodel.LanguageModel;

/**
 * Language grammar.
 * 
 * @author Luis Quesada (lquesada@modelcc.org) & Fernando Berzal (berzal@modelcc.org)
 */
public final class Grammar implements Serializable 
{
	/**
	 * Language model
	 */
	private LanguageModel model;

    /**
     * Set of rules.
     */
    private Set<Rule> rules;

    /**
     * Start type.
     */
    private Object startType;

    /**
     * Start rules.
     */
    private Map<Object,Set<Rule>> startRules;

    /**
     * Kleene's star
     */
    private Map<Object,Set<Object>> star;

    /**
     * Set of empty rules.
     */
    private Map<Object,Set<Object>> emptyRules;

    /**
     * Map of empty rules.
     */
    private Map<Object,Rule> emptyRuleMap;

    /**
     * The token symbol builder.
     */
    private SymbolBuilder tsb;
    
    /**
     * The default token symbol builder.
     */
    private static SymbolBuilder defaultTsb = new SymbolBuilder() 
    {
        @Override
        public boolean build(Symbol t, ParserMetadata data) {
            return true;
        }
    };
    
    /**
     * Default constructor
     */
    public Grammar ()
    {
        this.rules = new HashSet<Rule>();
        this.startType = null;
        this.tsb = defaultTsb;
    }
    

    /**
     * Prepare grammar for use.
     */
    public void prepare ()
    {
    	computeStartRules();
    	computeStar();
    }

	private void computeStartRules() 
	{
		this.startRules = new HashMap<Object,Set<Rule>>();

		for (Rule r: rules) {
		    int i = 0;
		    do {
		        Set<Rule> se = startRules.get(r.getRight().get(i).getType());
		        if (se == null) {
		            se = new HashSet<Rule>();
		            startRules.put(r.getRight().get(i).getType(),se);
		        }
		        se.add(r);
		        i++;
		    } while (emptyRules.containsKey(r.getRight().get(i-1).getType()) && i < r.getRight().size());
		}
	}

	private void computeStar() 
	{
		this.star = new HashMap<Object,Set<Object>>();

		Set<Object> objs = new HashSet<Object>();
		
		for (Rule r: rules) {
		    Set<Object> se = getStar(r.getLeft().getType());
		    se.add(r.getLeft().getType());
		    starFill(se,r,0,objs);
		    for (int i = 0;i < r.getRight().size();i++) {
		        se = getStar(r.getRight().get(i).getType());
		        se.add(r.getRight().get(i).getType());
		    }
		}

		boolean updated = true;

		while (updated) {
		    updated = false;
		    for (Object o: objs) {
		        for (Object o2: objs) {
		            if (star.get(o).contains(o2)) {
		            	for (Object o3: star.get(o2)) {
		            		if (!star.get(o).contains(o3)) {
		            			star.get(o).add(o3);
		            			updated = true;
		            		}
		            	}
		            }
		        }
		    }
		}
	}


    private void starFill(Set<Object> se, Rule r, int i, Set<Object> objs) 
    {
        se.add(r.getRight().get(i).getType());
        objs.add(r.getLeft().getType());
        objs.add(r.getRight().get(i).getType());
        if (emptyRules.containsKey(r.getRight().get(i).getType()) && r.getRight().size()>i+1) 
            starFill(se,r,i+1,objs);
    }

    
    // Getters & setters
    
    public LanguageModel getModel ()
    {
    	return model;
    }
    
    public void setModel (LanguageModel model)
    {
    	this.model = model;
    }

    public Set<Rule> getRules() 
    {
        return rules;
    }

    public Object getStartType() 
    {
        return startType;
    }
    
    public void setStartType (Object startType)
    {
    	this.startType = startType;
    }
    
    public Set<Object> getEmptyRules (Object object)
    {
    	return emptyRules.get(object);
    }
    
    public boolean isNullable (Object object)
    {
    	return emptyRules.containsKey(object);
    }

    public Rule getEmptyRule(Object object) 
    {
        return emptyRuleMap.get(object);
    }

    public Set<Rule> getStartRules(Object object) 
    {
        return startRules.get(object);
    }

    public Set<Object> getStar (Object object) 
    {
    	Set<Object> set = star.get(object);
    	
	    if (set == null) {
	        set = new HashSet<Object>();
	        star.put(object,set);
	    }
    	
        return set;
    }

    public SymbolBuilder getTokenSymbolBuilder() 
    {
        return tsb;
    }
    
    public void setTokenSymbolBuilder (SymbolBuilder tsb)
    {
        if (tsb == null)
            this.tsb = defaultTsb;
        else
    	   	this.tsb = tsb;
    }
    
    protected void setEmptyRules (Map<Object,Set<Object>> emptyRules, Map<Object,Rule> emptyRuleMap)
    {
    	this.emptyRules = emptyRules;
    	this.emptyRuleMap = emptyRuleMap;
    }
 
    // Grammar rules
    
    /**
     * Adds a rule.
     * @param r the rule to be added.
     */
    public void addRule(Rule r) 
    {
        if (r != null)
         rules.add(r);
    }
    
    /**
     * Removes a rule.
     * @param r the rule to be removed.
     */
    public void removeRule(Rule r) 
    {
        rules.remove(r);
    }
    
    // toString

    @Override
    public String toString() 
    {
        String ret = "";
        for (Rule r: rules)
            ret += r +"\n";
        ret += "\n";
        for (Object o: emptyRules.keySet())
            ret += "empty: "+o+"\n";
        return ret;    
    }

}
